﻿//https://leetcode.cn/problems/minimum-size-subarray-sum/
//暴力求解
class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		// 记录结果
		int ret = INT_MAX;
		int n = nums.size();
		// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
		// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
		// 枚举开始位置
		for (int start = 0; start < n; start++)
		{
			int sum = 0; // 记录从这个位置开始的连续数组的和
			// 寻找结束位置
			for (int end = start; end < n; end++)
			{
				sum += nums[end]; // 将当前位置加上
				if (sum >= target) // 当这段区间内的和满⾜条件时
				{
					// 更新结果，start 开头的最短区间已经找到
					ret = min(ret, end - start + 1);
					break;
				}
			}
		}
		// 返回最后结果
		return ret == INT_MAX ? 0 : ret;
	}
};
//我的
class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {

		int sum = 0, len = INT_MAX;
		int left = 0, right = 0;
		while (right < nums.size())
		{
			//进窗口       
			sum += nums[right];
			++right;

			//出窗口(条件成立 -》 判断是否更新len)
			while (sum >= target)
			{
				if (len > right - left)len = right - left;
				sum -= nums[left];
				++left;
			}
		}
		return len == INT_MAX ? 0 : len;
	}
};
//滑动窗口
class Solution
{
public:
	int minSubArrayLen(int target, vector<int>& nums)
	{
		int n = nums.size(), sum = 0, len = INT_MAX;
		for (int left = 0, right = 0; right < n; right++)
		{
			sum += nums[right]; // 进窗⼝
			while (sum >= target) // 判断
			{
				len = min(len, right - left + 1); // 更新结果
				sum -= nums[left++]; // 出窗⼝
			}
		}
		return len == INT_MAX ? 0 : len;
	}
};